package com.leetcode.www;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 * User:yxd
 * Date:2022-03-21
 * Time:20:27
 */
public class BFS653 {
    public boolean findTarget(TreeNode root, int k) {
        if(root == null)return false;
        Set<Integer> set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(set.contains(k - cur.val)){
                return true;
            }
            set.add(cur.val);
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        return false;

    }
}
